6251. Числовой трюк

 

Лукас должен провести презентацию о полезных математических трюках. Например, чтобы взять квадратный корень из числа, вам просто нужно удалить первую половину числа. Чтобы убедить свою аудиторию, он использует проверенный метод доказательства на примере:  = 5 и  = 76, то есть метод работает. Для умножения числа на x = 2.6 все, что Вам нужно сделать, - перенести первую цифру в конец числа, например 135 × 2.6 = 351 и 270270 × 2.6 = 702702.

Лукас хочет продемонстрировать, что последний метод работает для любого x. Для этого он просит свою аудиторию назвать значение x, после чего он покажет пример на умножение, для которого работает метод. Лукас заметил, что он не может просто выбрать произвольные числа для своих примеров, поэтому просит Вашей помощи. Можете ли Вы написать программу, которая по числу x выдаст список целых чисел, для которых умножение на x эквивалентно перемещению первой цифры в конец числа? Лукасу не нравятся очень большие цифры, поэтому не перечисляйте числа с более чем 8 цифрами.

 

Вход. Одно десятичное число x (1 ≤ x < 1000) с не более чем 4 десятичными цифрами.

 

Выход. Выведите список всех положительных целых чисел менее 108, на которых работает второй трюк Лукаса. Запишите числа в порядке возрастания, по одному в строке. Если список пуст, выведите No solution.

 

Пример входа 1

Пример выхода 1

2.6

135

270

135135

270270

 

 

Пример входа 2

Пример выхода 2

3.1416

No solution

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Пусть искомое число А имеет k + 1 цифру и начинается с цифры А0. Если первую цифру поставить в конец, то получим число (A – 10k *  А0) * 10 + А0, которое должно равняться A * x. Из равенства A * x = (A – 10k *  А0) * 10 + А0 следует что 10k+1 *  А0 – А0 = A (10 – x) или

Остается перебрать длину числа k (1 ≤ k + 1 ≤ 8 или 0 ≤ k < 8) и первую цифру А0, вычислить значение А и проверить является ли оно целым. Также следует проверить, является ли цифра А0 первой в числе А.

 

Реализация алгоритма

Определим константу епсилон.

 

#define EPS 0.000001

 

Читаем значение x.

 

scanf("%lf",&x);

p = 1; flag = 1;

 

Переменная p в цикле равна 10k. Если будет найдено хотя бы одно требуемое число, то установим flag = 0. Перебираем длину чисел k и первую цифру a0.

 

for (k = 0; k < 8; k++)

{

  for (a0 = 1; a0 < 10; a0++)

  {

 

Вычисляем значение А. Поскольку число x действительное, то деление совершается в действительных числах. Для корректного округления до ближайшего целого следует к частному прибавить 0.5.

 

    a = a0 * (p * 10 - 1) / (10 - x) + 0.5;

 

Цифра a0 будет первой в числе a, если a / p = a0. Помним, что у нас p = 10k и k в цикле начинается с 0 а не с 1. Далее следует проверить выполнение равенства (a – 10k *  a0) * 10 + А0 = A * x. Так как x действительное, то равенство x = y следует проверять как |x – y| < eps. Если сгенерированное число а удовлетворяет всем условиям, то выводим его на лету.

 

    if (a/p == a0 && abs((a - a0 * p) * 10 + a0 - x * a) < EPS)

    {

      printf("%lld\n",a);

      flag = 0;

    }

  }

  p = p * 10;

}

 

Если не было выведено ни одно число, то сообщаем об этом.

 

if (flag) printf("No solution\n");